"""
https://leetcode.cn/problems/maximum-subarray/description/

53. 最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

 

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：

输入：nums = [1]
输出：1
示例 3：

输入：nums = [5,4,-1,7,8]
输出：23
 

提示：

1 <= nums.length <= 105
-104 <= nums[i] <= 104
 

进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

"""

from typing import Dict, List


class Solution:
    """
    分治：
    最关键的两个问题是：
    - 我们要维护区间的哪些信息呢？
    - 我们如何合并这些信息呢？


    任意一个子数组，可以维护4个值：
    max_sum:最大连续和
    max_lsum:包含最左元素的最大连续和
    max_rsum包含最右元素的最大连续和

    如果一个数组nums，可以拆分为两个子数组a,b
    则max_sum(nums)=max(max_sum(a),max(sum_b),max_rsum(a)+max_lsum(b))
    max_lsum(nums)=max(sum(a)+max_lsum(b),max_lsum(a))
    max_rsum(nums)=max(sum(b)+max_rsum(a),max_rsum(b))
    由于用到了sum，可以把这个元素也设置为传递值

    否则该数组不可拆分的情况下，3个值均为该元素本身。

    此种方法可行，但实际效率略低，时间复杂度为nlog(n)

    """

    def maxSubArray(self, nums: List[int]) -> int:
        def max_obj(arr:List[int])->Dict[str,int]:
            if len(arr)==1:
                return {
                    'max_sum':arr[0],
                    'max_lsum':arr[0],
                    'max_rsum':arr[0],
                    'sum':arr[0]
                }
            mid=len(arr)//2
            left_arr=arr[0:mid]
            right_arr=arr[mid:len(arr)]
            left_max_obj=max_obj(left_arr)
            # print(left_arr,left_max_obj)
            right_max_obj=max_obj(right_arr)
            # print(right_arr,right_max_obj)
            return {
                'sum':left_max_obj['sum']+right_max_obj['sum'],
                'max_lsum':max(left_max_obj['sum']+right_max_obj['max_lsum'],left_max_obj['max_lsum']),
                'max_rsum':max(right_max_obj['sum']+left_max_obj['max_rsum'],right_max_obj['max_rsum']),
                'max_sum':max(left_max_obj['max_sum'],right_max_obj['max_sum'],left_max_obj['max_rsum']+right_max_obj['max_lsum'])
            }

        sum_res=max_obj(nums)
        # print(nums,sum_res)

        return sum_res['max_sum']


if __name__=='__main__':
    nums = [5,4,-1,7,8]

    s=Solution()
    res=s.maxSubArray(nums)
    print(res)
    pass